package leetcode_数组;

/**
 * 数组中的第 K 个最大元素
 * <p>算法: 快速排序</p>
 *
 * @author yezh
 * @date 2023/8/10 15:27
 */
public class _215 {

    public int findKthLargest(int[] nums, int k) {
        // 快排中没趟排序都会确定中枢位置
        return quickSort(0, nums.length - 1, k - 1, nums);
    }

    int quickSort(int start, int end, int k, int[] nums) {
        int first = nums[start], i = start, j = end;
        while (i < j) {
            while (i < j && nums[j] <= first) --j;
            nums[i] = nums[j];
            while (i < j && nums[i] >= first) ++i;
            nums[j] = nums[i];
        }
        nums[i] = first;
        if (i > k) return quickSort(start, i - 1, k, nums);
        if (i < k) return quickSort(i + 1, end, k, nums);
        return nums[i];
    }

}
